package Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-31  23:16
 * @Description: TODO
 * @Version: 1.0
 */
public class 在每个树行中找最大值515 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 采用广度遍历是简单的 层序遍历找到每一层中最大的即可加入
    // 这个采用的层序遍历的方式来实现
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        // 0 表示深度
        dfs(root, list, 0);
        return list;
    }

    private void dfs(TreeNode root, List<Integer> list, int depth) {
        if (depth == list.size()) {
            list.add(root.val);
        } else {
            list.set(depth, Math.max(list.get(depth), root.val));
        }
        if (root.left != null) {
            depth++;
            dfs(root.left, list, depth);
            depth--;
        }
        if (root.right != null) {
            depth++;
            dfs(root.right, list, depth + 1);
            depth--;
        }
    }
}
